//给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。 
//
// 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上
//方移动，可以移动的前提是到达的格子没有障碍。 
//
// 一条路径的 「得分」 定义为：路径上所有数字的和。 
//
// 请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。 
//
// 如果没有任何路径可以到达终点，请返回 [0, 0] 。 
//
// 
//
// 示例 1： 
//
// 
//输入：board = ["E23","2X2","12S"]
//输出：[7,1]
// 
//
// 示例 2： 
//
// 
//输入：board = ["E12","1X1","21S"]
//输出：[4,2]
// 
//
// 示例 3： 
//
// 
//输入：board = ["E11","XXX","11S"]
//输出：[0,0]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= board.length == board[i].length <= 100 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 82 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//java:最大得分的路径数目
public class Q1301NumberOfPathsWithMaxScore {
    public static void main(String[] args){
        Solution solution = new Q1301NumberOfPathsWithMaxScore().new Solution();
        solution.pathsWithMaxScore(new ArrayList<String>(){{
            add("E11345");
            add("X452XX");
            add("3X43X4");
            add("44X312");
            add("23452X");
            add("1342XS");
        }});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        int mod = (int) 1e9 + 7;
        int[][] dp = new int[n][n];
        int[][] count = new int[n][n];
        char[][] chars = new char[n][n];
        int[][] directions = {{0,1},{1,0},{1,1}};
        for (int i = 0; i < n; i++) {
            chars[i] = board.get(i).toCharArray();
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                // 当前点是起点, 方案数为1，最远路径为 0
                if (chars[i][j] == 'S') {
                    dp[i][j] = 0;
                    count[i][j] = 1;
                    continue;
                }

                // 当前节点是X
                if (chars[i][j] == 'X') {
                    dp[i][j] = 0;
                    count[i][j] = 0;
                    continue;
                }

                // 考虑三个方向的
                for (int[] direction : directions) {
                    int curI = i + direction[0], curJ = j + direction[1];
                    if (curI >= n || curJ >= n || chars[curI][curJ] == 'X' || (count[curI][curJ] == 0 && dp[curI][curJ] == 0)) continue;
//                    if (curI >= n || curJ >= n || chars[curI][curJ] == 'X') continue;
                    // 当前位置的新值，如果是结束字符就为0
                    int value = dp[curI][curJ] + (chars[i][j] == 'E' ? 0 : chars[i][j] - '0');
                    if (dp[i][j] < value) {
                        dp[i][j] = value;
                        dp[i][j] %= mod;
                        count[i][j] = count[curI][curJ];
                    } else if (dp[i][j] == value) {
                        count[i][j] += count[curI][curJ];
                        count[i][j] %= mod;
                    }
                }
            }
        }
        return new int[]{dp[0][0], count[0][0]};
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}